This video introduces us to the Greedy Algorithms and its various Applications.
Codes:
- Minimum Coins
This track of the course covers the topic "Greedy Algorithms".
In details, this track will cover:
Objective: The objective of this track is to familiarize learners with Greedy Algorithms.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
This video introduces us to the Greedy Algorithms and its various Applications.
Codes:
This video discusses the Activity Selection Problem.
This video talks about C++ Solution of Activity Selection Problem.
Codes:
This video talks about Java Solution of Activity Selection Problem.
Codes:
This video discusses the Fractional Knapsack Problem.
This video talks about C++ implementation of Fractional Knapsack problem.
Codes:
This video talks about Java implementation of the Greedy Algorithm for Fraction Knapsack problem
Codes:
This video discusses the working and the concept behind the famous Job Sequencing Problem
Given a list of elements with specific values and weights associated with them, the task is to fill a Knapsack of weight W using these elements such that the value of knapsack is maximum possible.
Note: You are allowed to take a fraction of an element also in order to maximize the value.

At every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem.
Example 1: Consider the following 3 activities sorted by
finish time.
start[] = {10, 12, 20};
finish[] = {20, 25, 30};
A person can perform at most two activities. The
maximum set of activities that can be executed
is {0, 2} [ These are indexes in start[] and
finish[] ]
Example 2: Consider the following 6 activities
sorted by finish time.
start[] = {1, 3, 0, 5, 8, 5};
finish[] = {2, 4, 6, 7, 9, 9};
A person can perform at most four activities. The
maximum set of activities that can be executed
is {0, 1, 3, 4} [ These are indexes in start[] and
finish[] ]
Input: Four Jobs with following deadlines and profits
JobID Deadline Profit
a 4 20
b 1 10
c 1 40
d 1 30
Output: Following is maximum profit sequence of jobs
c, a
Input: Five Jobs with following deadlines and profits
JobID Deadline Profit
a 2 100
b 1 19
c 2 27
d 1 25
e 3 15
Output: Following is maximum profit sequence of jobs
c, a, e
1) Sort all jobs in decreasing order of profit.
2) Initialize the result sequence as the first job in sorted jobs.
3) Do following for remaining n-1 jobs
.......a) If the current job can fit in the current result sequence
without missing the deadline, add the current job to the result.
Else ignore the current job.
// C++ program to find the maximum profit
// job sequence from a given array
// of jobs with deadlines and profits
#include<iostream>
#include<algorithm>
using namespace std;
// A structure to represent a job
struct Job
{
char id; // Job Id
int dead; // Deadline of job
// Profit if job is over
// before or on deadline
int profit;
};
// This function is used for sorting all
// jobs according to profit
bool comparison(Job a, Job b)
{
return (a.profit > b.profit);
}
// Returns minimum number of platforms reqquired
void printJobScheduling(Job arr[], int n)
{
// Sort all jobs according to
// decreasing order of prfit
sort(arr, arr+n, comparison);
int result[n]; // To store result (Sequence of jobs)
bool slot[n]; // To keep track of free time slots
// Initialize all slots to be free
for (int i=0; i<n; i++)
slot[i] = false;
// Iterate through all given jobs
for (int i=0; i<n; i++)
{
// Find a free slot for this job
// (Note that we start
// from the last possible slot)
for (int j=min(n, arr[i].dead)-1; j>=0; j--)
{
// Free slot found
if (slot[j]==false)
{
result[j] = i; // Add this job to result
slot[j] = true; // Make this slot occupied
break;
}
}
}
// Print the result
for (int i=0; i<n; i++)
if (slot[i])
cout << arr[result[i]].id << " ";
}
// Driver Code
int main()
{
Job arr[] = { {'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27},
{'d', 1, 25}, {'e', 3, 15}};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Following is maximum profit sequence of job : ";
printJobScheduling(arr, n);
return 0;
}
// Java program to find the maximum profit
// job sequence from a given array
// of jobs with deadlines and profits
import java.util.Arrays;
// A class to represent a job
class Job implements Comparable<Job>
{
char id; // Job Id
int dead; // Deadline of job
// Profit if job is over
// before or on deadline
int profit;
Job(char id, int dead, int profit) {
this.id = id;
this.dead = dead;
this.profit = profit;
}
// This function is used for sorting all
// jobs according to decreasing order of profit
@Override
public int compareTo(Job o) {
if(this.profit < o.profit)
return 1;
return -1;
}
};
class GFG
{
// Returns minimum number of platforms reqquired
static void printJobScheduling(Job arr[], int n)
{
// Sort all jobs according to
// decreasing order of prfit
Arrays.sort(arr);
// To store result (Sequence of jobs)
int result[] = new int[n];
// To keep track of free time slots
boolean slot[] = new boolean[n];
// Initialize all slots to be free
for (int i=0; i<n; i++)
slot[i] = false;
// Iterate through all given jobs
for (int i=0; i<n; i++)
{
// Find a free slot for this job
// (Note that we start
// from the last possible slot)
for (int j=Math.min(n, arr[i].dead)-1; j>=0; j--)
{
// Free slot found
if (slot[j]==false)
{
result[j] = i; // Add this job to result
slot[j] = true; // Make this slot occupied
break;
}
}
}
// Print the result
for (int i=0; i<n; i++)
if (slot[i])
System.out.print(arr[result[i]].id + " ");
}
// Driver Code
public static void main(String args[])
{
Job arr[] = {new Job('a', 2, 100),
new Job('b', 1, 19),
new Job('c', 2, 27),
new Job('d', 1, 25),
new Job('e', 3, 15)};
int n = arr.length;
System.out.print("Following is maximum profit"
+" sequence of job : ");
printJobScheduling(arr, n);
}
}Following is maximum profit sequence of job : c a e
Asked In: Facebook Morgan Stanley
Asked In: Amazon Flipkart MakeMyTrip Microsoft
Asked In: Microsoft
Asked In: Microsoft
A | P, Q, R, S, T, U |
B | P, Q, R, U, S, T |
C | P, Q, R, U, T, S |
D | P, Q, T, R, U, S |